package com.itheima.leetcode.od.b.bf;

import java.util.Arrays;

/**
 * (A卷,100分)- 租车骑绿岛（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 部门组织绿岛骑行团建活动。租用公共双人自行车，每辆自行车最多坐两人，最大载重M。
 * 给出部门每个人的体重，请问最多需要租用多少双人自行车。
 * <p>
 * 输入描述
 * <p>
 * 第一行两个数字m、n，分别代表自行车限重，部门总人数。
 * <p>
 * 第二行，n个数字，代表每个人的体重，体重都小于等于自行车限重m。
 * <p>
 * 0<m<=200
 * 0<n<=1000000
 * <p>
 * 输出描述
 * <p>
 * 最小需要的双人自行车数量。
 * <p>
 * 用例
 * <p>
 * 输入	3 4
 * 3 2 2 1
 * 输出	3
 * 说明	无
 * <p>
 * 题目解析
 * <p>
 * 本题需要最少的车辆，即尽可能组合出重量小于等于m的两人组。
 * <p>
 * 首先，我们可以将所有人按体重升序，然后将最大体重和m比较，若最大体重大于等于m，则这个人只能一人占一辆车，车数量count++，然后将最大体重弹出，继续将剩下体重中最大的和m比较，逻辑同上，直到最大体重小于m时，停止弹出。
 * <p>
 * 在剩余体重中，我们利用双指针，i指针指向最小体重，j指针指向最大体重，然后组合它们，即arr[i]+arr[j]，和m比较，若小于等于m，则说明这两个人可以共享一辆车，车数量count++，然后i++，j--。如果arr[i]+arr[j]>m，则说明两个人无法共享一辆车，我们只能优先将这里车分配给较大体重的人，此时车数量count++，然后j--。
 * <p>
 * 按上面逻辑移动双指针，最后可能会出现两种情况：
 * <p>
 * i > j        此情况下所有人均分配到了车，因此可以直接输出count作为题解
 * i === j    此情况下还有一个人未分配到车，因此需要count++，为这个人单独分配一辆车
 */
public class RidingOnGreenIsland {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();
        int n = sc.nextInt();

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }*/

        int m = 3;
        int n = 4;

        String input = "3 2 2 1";
        int[] arr = Arrays.stream(input.split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        System.out.println(getResult(arr, m));
    }

    /**
     * 两数之和（变体版）
     *
     * @param arr
     * @param m
     * @return
     */
    public static int getResult(int[] arr, int m) {
        Arrays.sort(arr);

        int count = 0;

        int i = 0;
        int j = arr.length - 1;

        while (i < j) {
            if (arr[i] + arr[j] <= m) {
                i++;
            }
            j--;
            count++; // 两人超重就直接单人骑车
        }

        if (i == j) { // 等于情况下表明剩一个人，只能单人骑车
            count++;
        }

        return count;
    }
}